#include <bits/stdc++.h>

using namespace std;

const int N = 2e5 + 100;
int T,n,ans,anss,ans1,ans2;
int a[N],dp[N][3][3][3],c[N],q[N];

void read(int &res){
    int x = 0,w = 1;
    char ch = 0;
    while(ch < '0' || ch > '9'){
        if(ch == '-') w = -1;
        ch = getchar();
    }
    while(ch >= '0' && ch <= '9'){
        x = (x<<3) + (x<<1) + (ch-'0');
        ch = getchar();
    }
    res = x * w;
}

void init(){
    memset(dp,0,sizeof(dp));
    ans = 0;
}

void dfs(int cur,int col){
    q[cur] = col;
    if(cur == n){
        memset(c,0,sizeof(c));
        for(int i = 1;i <= n;i++){
            for(int j = i - 1;j >= 1;j--){
                if(q[i] == q[j]){
                    if(a[i] == a[j]){
                        c[i] = a[i];
                    }
                    break;
                }
            }
        }
        int tm = 0;
        for(int i = 1;i <= n;i++) tm += c[i];
        anss = max(anss,tm);
        return ;
    }
    dfs(cur + 1,1);
    dfs(cur + 1,2);
}

void force(){
    anss = 0;
    dfs(1,1);
    dfs(1,2);
    printf("%d\n",anss);
}

int main(){
    freopen("color.in","r",stdin);
    freopen("color.out","w",stdout);
    read(T);
    while(T--){
        init();
        //printf("Rest : %d\n",T);
        read(n);
        for(int i = 1;i <= n;i++) read(a[i]);
        if(n <= 15){
            force();
            continue;
        }
        //printf("n = %d\n",n);
        if(n > 2000){
            printf("0\n");
            continue;
        }
        for(int i = 2;i <= n;i++){
            dp[i][0][0][1] = max(dp[i-1][1][0][0],dp[i-1][1][0][1]);
            dp[i][1][1][0] = max(dp[i-1][0][0][0],dp[i-1][0][1][0]);
            for(int j = i - 1;j >= 1;j--){
                int del = 0;
                if(a[i] == a[j]) del = a[i];
                dp[i][0][1][0] = max(dp[i][0][1][0],max(max(dp[j][0][0][0] + del,dp[j][0][0][1] + del),max(dp[j][0][1][0] + del,dp[j][0][1][1] + del)));
                dp[i][0][1][1] = max(dp[i][0][1][1],max(max(dp[j][0][0][0] + del,dp[j][0][0][1] + del),max(dp[j][0][1][0] + del,dp[j][0][1][1] + del)));
                dp[i][1][0][1] = max(dp[i][1][0][1],max(max(dp[j][1][0][0] + del,dp[j][1][0][1] + del),max(dp[j][1][1][0] + del,dp[j][1][1][1] + del)));
                dp[i][1][1][1] = max(dp[i][1][1][1],max(max(dp[j][1][0][0] + del,dp[j][1][0][1] + del),max(dp[j][1][1][0] + del,dp[j][1][1][1] + del)));
            }
        }
        ans = 0;
        for(int i1 = 0;i1 <= 1;i1++){
            for(int i2 = 0;i2 <= 1;i2++){
                for(int i3 = 0;i3 <= 1;i3++){
                    ans = max(ans,dp[n][i1][i2][i3]);
                }
            }
        }
        printf("%d\n",ans);
        //printf("\n");
    }
    return 0;
}
